package com.dataStructure.树.红黑树;

import java.util.Comparator;

public class RBTree<E> extends BBST<E> {
    private static final boolean RED = false;
    private static final boolean BLACK = true;

    //构造方法同样也要传入比较器
    public RBTree() {
        this(null);
    }

    public RBTree(Comparator<E> comparator) {
        super(comparator);
    }

    @Override
    protected Node<E> createNode(E element, Node<E> parent) {
        return new RBNode<>(element, parent);
    }

    private static class RBNode<E> extends Node<E> {
        //颜色 使用color = RED,color = BLACK给颜色赋值
        //优先使用红色可以使红黑树的性质快速满足
        boolean color = RED;

        public RBNode(E element, Node<E> parent) {
            super(element, parent);
        }

        @Override
        public String toString() {
            String str = "";
            if (color == RED) {
                str = "_R";
            }
            return str + element.toString();
        }
    }

    //上色，给node和想染的颜色
    private Node<E> color(Node<E> node, boolean color) {
        if (node == null) return null;
        ((RBNode<E>) node).color = color;
        return node;
    }

    //染成红色
    private Node<E> red(Node<E> node) {
        return color(node, RED);
    }

    //染成黑色
    private Node<E> black(Node<E> node) {
        return color(node, BLACK);
    }

    //得到传入节点的颜色
    private boolean colorOf(Node<E> node) {
        //空的返回黑色
        return node == null ? BLACK : ((RBNode<E>) node).color;
    }

    //判断是否为黑色
    private boolean isBlack(Node<E> node) {
        return colorOf(node) == BLACK;
    }

    //判断是否为红色
    private boolean isRed(Node<E> node) {
        return colorOf(node) == RED;
    }

    //添加之后，如果不是红黑树要进行相应的恢复
    @Override
    protected void afterAdd(Node<E> node) {
        //拿到插入节点的父节点
        Node<E> parent = node.parent;

        //添加的是根节点或者上溢到了根节点
        if (parent == null) {
            //染黑
            black(node);
            return;
        }

        //如果父节点是黑色不用做任何处理
        if (isBlack(parent)) return;

        //来到这里说明父节点是红色了
        //拿到uncle节点进行判断
        Node<E> uncle = parent.sibling();
        //祖父节点
        Node<E> grand = parent.parent;
        //如果uncle节点是红色，红色即上溢
        if (isRed(uncle)) {
            black(uncle);
            black(parent);
            //把祖父节点当做是新添加的节点
            afterAdd(red(grand));
            return;
        }

        //如果uncle节点不是红色
        if (parent.isLeftChild()) {//父节点是左子树
            //LL
            if (node.isLeftChild()) {
                black(parent);
                red(grand);
                rotateRight(grand);
                //LR
            } else {
                black(node);
                red(grand);
                rotateLeft(parent);
                rotateRight(grand);
            }
        } else {//父节点是右子树
            //RL
            if (node.isLeftChild()) {
                black(node);
                red(grand);
                rotateRight(parent);
                rotateLeft(grand);
                //RR
            } else {
                black(parent);
                red(grand);
                rotateLeft(grand);
            }
        }
    }

    //删除之后，如果不是红黑树要进行相应的恢复
    @Override
    protected void afterRmove(Node<E> node, Node<E> replacement) {
        //如果删除的节点是红色
        // 直接删除不作任何处理
        if (isRed(node)) return;

        //如果删除的节点是黑色

        //如果这个黑色节点有子树节点
        //如果用以取代node节点的子节点replacement是红色
        //无论node节点有几个子树，replacement
        if (isRed(replacement)) {
            black(replacement);
            return;
        }

        Node<E> parent = node.parent;
        //删除的黑色节点是根节点
        if (parent == null) return;

        //黑色节点是叶子节点

        //如果兄弟节点是黑色
        //不能通过Node<E> sibling = node.sibling();来拿到我的兄弟节点，因为这个方法是基于node来拿到兄弟节点，但是在这之前node可能已经被删除所以拿不准
        //通过以下方式拿到兄弟节点,判断其父节点的左子树是不是空的，如果是空的那么右子树就是兄弟节点，反之亦然
        boolean left = parent.left == null || node.isLeftChild();
        Node<E> sibling = left ? parent.right : parent.left;
        if (left) {//被删除的节点在左边，兄弟节点在右边,对称操作

            if (isRed(sibling)) {//如果兄弟节点是红色
                //旋转操作，把兄弟节点转换成黑色
                black(sibling);
                red(parent);
                rotateLeft(parent);
                //更换兄弟节点
                sibling = parent.right;
            }
            //统一处理兄弟节点是黑色的情况

            //兄弟节点左右都是黑，借不出来，只能父节点向下跟兄弟节点合并
            if (isBlack(sibling.left) && isBlack(sibling.right)) {
                boolean parentBlack = isBlack(parent);
                black(parent);
                red(sibling);

                //如果父节点是黑色，向下合并后就空了，需要将向下合并的父节点当做被删除，再处理来一次
                if (parentBlack) {
                    afterRmove(parent, null);
                }

                //兄弟节点左右至少有一个是红的，可以借向兄弟节点借元素
            } else {
                //借元素是旋转操作，当是LR类型的借元素时，先进行左旋转，再进行右旋转，这里先处理一下左旋转，然后统一处理右旋转
                //当兄弟节点是左边是黑的（null）时进行左旋转
                if (isBlack(sibling.right)) {
                    rotateRight(sibling);
                    sibling = parent.right;
                }
                //统一进行右旋转

                //先染色,染成parent的颜色，后右旋转
                color(sibling, colorOf(parent));
                black(sibling.right);
                black(parent);
                rotateLeft(parent);
            }
        } else {//被删除的节点在右边，兄弟节点在左边
            if (isRed(sibling)) {//如果兄弟节点是红色
                //旋转操作，把兄弟节点转换成黑色
                black(sibling);
                red(parent);
                rotateRight(parent);
                //更换兄弟节点
                sibling = parent.left;
            }
            //统一处理兄弟节点是黑色的情况

            //兄弟节点左右都是黑，借不出来，只能父节点向下跟兄弟节点合并
            if (isBlack(sibling.left) && isBlack(sibling.right)) {
                boolean parentBlack = isBlack(parent);
                black(parent);
                red(sibling);

                //如果父节点是黑色，向下合并后就空了，需要将向下合并的父节点当做被删除，再处理来一次
                if (parentBlack) {
                    afterRmove(parent, null);
                }

                //兄弟节点左右至少有一个是红的，可以借向兄弟节点借元素
            } else {
                //借元素是旋转操作，当是LR类型的借元素时，先进行左旋转，再进行右旋转，这里先处理一下左旋转，然后统一处理右旋转
                //当兄弟节点是左边是黑的（null）时进行左旋转
                if (isBlack(sibling.left)) {
                    rotateLeft(sibling);
                    sibling = parent.left;
                }
                //统一进行右旋转
                //先染色,染成parent的颜色，后右旋转
                color(sibling, colorOf(parent));
                black(sibling.left);
                black(parent);
                rotateRight(parent);
            }
        }
    }
}